package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC87 {


    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * @return:
     */

    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if (s1.equals(s2)) return true;
        int[] hash = new int[26];

        for (int i = 0; i < s1.length(); i++)
            hash[s1.charAt(i) - 'a']++;

        for (int j = 0; j < s2.length(); j++)
            hash[s2.charAt(j) - 'a']--;

        for (int k = 0; k < 26; k++) {
            if (hash[k] != 0)
                return false;
        }

        for (int i = 1; i < s1.length(); i++) {
            if (
                    (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i)))
                            || (isScramble(s1.substring(0, i), s2.substring(s1.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s1.length() - i)))
                    )
                return true;

        }
        return false;
    }


    public static void main(String[] args) {
        LC87 an = new LC87();
        System.out.println(an.isScramble("rgtae", "great"));
    }
}
